//! B+树索引测试
//! 
//! 测试B+树索引的核心功能

#[cfg(test)]
mod tests {
    use super::super::btree::*;
    use crate::sql::Value;
    use std::collections::HashSet;

    #[test]
    fn test_btree_basic_operations() {
        let mut btree = BPlusTree::new(3); // 度数为3的B+树
        
        // 测试插入
        assert!(btree.insert(Value::Integer(10), 1).is_ok());
        assert!(btree.insert(Value::Integer(20), 2).is_ok());
        assert!(btree.insert(Value::Integer(5), 3).is_ok());
        assert!(btree.insert(Value::Integer(15), 4).is_ok());
        
        // 测试查找
        assert_eq!(btree.search(&Value::Integer(10)), Some(1));
        assert_eq!(btree.search(&Value::Integer(20)), Some(2));
        assert_eq!(btree.search(&Value::Integer(5)), Some(3));
        assert_eq!(btree.search(&Value::Integer(15)), Some(4));
        assert_eq!(btree.search(&Value::Integer(100)), None);
        
        // 测试删除
        assert!(btree.delete(&Value::Integer(10)).is_ok());
        assert_eq!(btree.search(&Value::Integer(10)), None);
        assert_eq!(btree.search(&Value::Integer(20)), Some(2));
    }
    
    #[test]
    fn test_btree_range_query() {
        let mut btree = BPlusTree::new(3);
        
        // 插入测试数据
        for i in 1..=20 {
            btree.insert(Value::Integer(i), i as usize).unwrap();
        }
        
        // 测试范围查询
        let result = btree.range_search(&Value::Integer(5), &Value::Integer(15));
        let expected: HashSet<usize> = (5..=15).collect();
        let actual: HashSet<usize> = result.into_iter().collect();
        assert_eq!(actual, expected);
        
        // 测试边界情况
        let result = btree.range_search(&Value::Integer(1), &Value::Integer(3));
        assert_eq!(result.len(), 3);
        assert!(result.contains(&1));
        assert!(result.contains(&2));
        assert!(result.contains(&3));
    }
    
    #[test]
    fn test_btree_large_dataset() {
        let mut btree = BPlusTree::new(5);
        let n = 1000;
        
        // 插入大量数据
        for i in 0..n {
            btree.insert(Value::Integer(i), i as usize).unwrap();
        }
        
        // 验证所有数据都能找到
        for i in 0..n {
            assert_eq!(btree.search(&Value::Integer(i)), Some(i as usize));
        }
        
        // 测试范围查询性能
        let start = std::time::Instant::now();
        let result = btree.range_search(&Value::Integer(100), &Value::Integer(200));
        let elapsed = start.elapsed();
        
        assert_eq!(result.len(), 101); // 100到200包含101个数
        assert!(elapsed.as_millis() < 10); // 应该在10ms内完成
    }
    
    #[test]
    fn test_btree_split_and_merge() {
        let mut btree = BPlusTree::new(3); // 小度数，容易触发分裂
        
        // 插入足够多的数据触发节点分裂
        for i in 1..=10 {
            btree.insert(Value::Integer(i), i as usize).unwrap();
        }
        
        // 验证树结构正确
        assert!(btree.height() > 1); // 应该有多层
        
        // 验证所有数据仍然可以找到
        for i in 1..=10 {
            assert_eq!(btree.search(&Value::Integer(i)), Some(i as usize));
        }
        
        // 删除数据，可能触发合并
        for i in 1..=5 {
            btree.delete(&Value::Integer(i)).unwrap();
        }
        
        // 验证删除后的数据
        for i in 1..=5 {
            assert_eq!(btree.search(&Value::Integer(i)), None);
        }
        for i in 6..=10 {
            assert_eq!(btree.search(&Value::Integer(i)), Some(i as usize));
        }
    }
    
    #[test]
    fn test_btree_duplicate_keys() {
        let mut btree = BPlusTree::new(3);
        
        // 插入重复键
        assert!(btree.insert(Value::Integer(10), 1).is_ok());
        assert!(btree.insert(Value::Integer(10), 2).is_ok()); // 应该支持重复键
        
        // 查找应该返回其中一个值
        let result = btree.search(&Value::Integer(10));
        assert!(result == Some(1) || result == Some(2));
        
        // 范围查询应该返回所有匹配的值
        let results = btree.range_search(&Value::Integer(10), &Value::Integer(10));
        assert!(results.len() >= 1);
    }
    
    #[test]
    fn test_btree_string_keys() {
        let mut btree = BPlusTree::new(3);
        
        // 测试字符串键
        btree.insert(Value::Text("apple".to_string()), 1).unwrap();
        btree.insert(Value::Text("banana".to_string()), 2).unwrap();
        btree.insert(Value::Text("cherry".to_string()), 3).unwrap();
        
        assert_eq!(btree.search(&Value::Text("apple".to_string())), Some(1));
        assert_eq!(btree.search(&Value::Text("banana".to_string())), Some(2));
        assert_eq!(btree.search(&Value::Text("cherry".to_string())), Some(3));
        
        // 测试字符串范围查询
        let results = btree.range_search(
            &Value::Text("a".to_string()), 
            &Value::Text("c".to_string())
        );
        assert!(results.contains(&1)); // apple
        assert!(results.contains(&2)); // banana
    }
    
    #[test]
    fn test_btree_concurrent_access() {
        use std::sync::{Arc, Mutex};
        use std::thread;
        
        let btree = Arc::new(Mutex::new(BPlusTree::new(5)));
        let mut handles = vec![];
        
        // 多线程并发插入
        for thread_id in 0..4 {
            let btree_clone = btree.clone();
            let handle = thread::spawn(move || {
                for i in 0..100 {
                    let key = thread_id * 100 + i;
                    let mut tree = btree_clone.lock().unwrap();
                    tree.insert(Value::Integer(key), key as usize).unwrap();
                }
            });
            handles.push(handle);
        }
        
        // 等待所有线程完成
        for handle in handles {
            handle.join().unwrap();
        }
        
        // 验证所有数据都插入成功
        let tree = btree.lock().unwrap();
        for thread_id in 0..4 {
            for i in 0..100 {
                let key = thread_id * 100 + i;
                assert_eq!(tree.search(&Value::Integer(key)), Some(key as usize));
            }
        }
    }
    
    #[test]
    fn test_btree_performance() {
        let mut btree = BPlusTree::new(100); // 大度数，减少树高度
        let n = 10000;
        
        // 测试插入性能
        let start = std::time::Instant::now();
        for i in 0..n {
            btree.insert(Value::Integer(i), i as usize).unwrap();
        }
        let insert_time = start.elapsed();
        
        // 测试查找性能
        let start = std::time::Instant::now();
        for i in 0..n {
            assert_eq!(btree.search(&Value::Integer(i)), Some(i as usize));
        }
        let search_time = start.elapsed();
        
        // 测试范围查询性能
        let start = std::time::Instant::now();
        let _results = btree.range_search(&Value::Integer(1000), &Value::Integer(2000));
        let range_time = start.elapsed();
        
        println!("B+树性能测试 ({}条记录):", n);
        println!("插入时间: {:?}", insert_time);
        println!("查找时间: {:?}", search_time);
        println!("范围查询时间: {:?}", range_time);
        
        // 性能要求
        assert!(insert_time.as_millis() < 1000); // 插入应该在1秒内完成
        assert!(search_time.as_millis() < 500);  // 查找应该在0.5秒内完成
        assert!(range_time.as_millis() < 100);   // 范围查询应该在0.1秒内完成
    }
    
    #[test]
    fn test_btree_memory_usage() {
        let mut btree = BPlusTree::new(10);
        let n = 1000;
        
        // 插入数据
        for i in 0..n {
            btree.insert(Value::Integer(i), i as usize).unwrap();
        }
        
        // 检查内存使用情况
        let memory_usage = btree.memory_usage();
        println!("B+树内存使用: {} bytes", memory_usage);
        
        // 内存使用应该合理（每个节点不应该过大）
        assert!(memory_usage > 0);
        assert!(memory_usage < 1024 * 1024); // 应该小于1MB
    }
}
